Basic version: implement a two-player game letting two different algorithms / sets of parameters play against each other. Basic version: implement an alpha-beta pruning algorithm so that it stops computation and returns the best move found so far, when it runs out of "wallclock" time. Extension 2: propose / code a modification of -- e.g. If the sum of times spent on selecting a move by a given player exceeds this time, that player loses. You can assume, that a player "thinks" only during its move (when you do not want to use multithreading).

An analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. A formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform tree of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution. A worst case analysis over all possible probability distributions is then presented by considering the limiting case when the discrete probability distribution tends to a continuous probability distribution. The branching factor of the alpha-beta pruning algorithm is shown to grow with n as Θ(n/lnn), therefore confirming a claim by Knuth and Moore that deep cut-offs only have a second order effect on the behavior of the algorithm.

Dept. of Computer Science, Carnegie-Mellon University. "Many game-playing programs must search very large game trees. Use of the alpha-beta pruning algorithm instead of the simple minimax search reduces by a large factor the number of bottom positions which must be examined in the search. An analytical expression for the expected number of bottom positions examined in a game tree using alpha-beta pruning is derived, subject to the assumptions that the branching factor N and the depth D of the tree are arbitrary but fixed, and the bottom positions are a random permutation of ND unique values. A simple approximation to the growth rate of the expected number of bottom positions examined is suggested, based on a Monte Carlo simulation for large values of N and D. The behavior of the model is compared with the behavior of the alpha-beta algorithm in a chess playing program and the effects of correlation and non-unique bottom position values in real game trees are examined."